﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//#define size 10
//int main()
//{
//
//	char c[5] = { 'a','b','\0','c','\0' }; 
//	printf("%s", c);
//
//	char a[size], b[size + 2];
//	return 0;
//}


//编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内(0~127 ，包括 0 和 127)，换行表示结束符，
//不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
//例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。
//数据范围：
//1≤n≤500
//输入描述：
//输入一行没有空格的字符串。
//
//输出描述：
//输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。

//int cmp(const void* x, const void* y)
//{
//	return *(char*)x - *(char*)y;
//}
//
//int main()
//{
//	char arr[505];
//	scanf("%s", arr);
//	int len = strlen(arr);
//	qsort(arr, len, sizeof(char), cmp);
//	int i = 1, count = 1;
//	if (len == 1)
//	{
//		;
//	}
//	else
//	{
//		for (int i = 1; i < len; i++)
//		{
//			if (arr[i] == arr[i - 1])
//			{
//				continue;
//			}
//			else
//			{
//				count++;
//			}
//		}
//	}
//	printf("%d", count);
//	return 0;
//}

//
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。

//int cmp(const void* x, const void* y)
//{
//	return *(int*)x - *(int*)y;
//}
//
//int majorityElement(int* nums, int numsSize)
//{
//	int num = numsSize / 2;
//	if (numsSize == 1)
//	{
//		return nums[0];
//	}
//	qsort(nums, numsSize, sizeof(int), cmp);//快速排序，把相同的放在一起方便后续的比较
//	int count = 1;
//	int i = 0;
//	for ( i = 1; i < numsSize; i++)
//	{
//		if (count > num)//开始循环之前先判断count是不是已经超过num了
//		{
//			break;
//		}
//		if (nums[i] == nums[i - 1])
//		{
//			count++;
//		}
//		else//发现不相等，重置count为1
//		{
//			count = 1;
//		}
//	}
//	return nums[i - 1];
//}


//int main()
//{
//	int a[12] = { 1,2,3,4,5,6,7,8,9,10,11,12 } ,* p[4],i;
//	for (i = 0; i < 4; i++)
//		p[i] = &a[i * 3];
//	printf("%d\n",p[3][2]);
//	return 0;
//}


//自除数 是指可以被它包含的每一位数整除的数。
//
//例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
//自除数 不允许包含 0 。
//
//给定两个整数 left 和 right ，返回一个列表，列表的元素是范围[left, right] 内所有的 自除数 。

//int* selfDividingNumbers(int left, int right, int* returnSize)
//{
//	int* arr = (int*)malloc(sizeof(int) * (right - left + 1));//分配空间
//	int ret, count = 0, j = 0, flag = 1;//count计数，j是arr数组下标，通过flag是否为1判断自除数是否判断成功
//	for (int i = left; i <= right; i++)//遍历
//	{
//		int num = i;
//		while (num)
//		{
//			flag = 1;
//			ret = num % 10;
//			if ((ret == 0) || i % ret != 0)
//			{
//				flag = 0;
//				break;
//			}
//			num = num / 10;
//		}
//		if (flag)
//		{
//			count++;
//			arr[j++] = i;
//		}
//	}
//	*returnSize = count;
//	return arr;
//}


//给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
//
//题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
//
//请 不要使用除法，且在 O(n) 时间复杂度内完成此题。


int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    //用两个辅助数组，其中分别记录此时i的前缀乘积与后缀乘积
    int* prefix = (int*)malloc(sizeof(int) * numsSize);
    int* suffix = (int*)malloc(sizeof(int) * numsSize);
    int* answer = (int*)malloc(sizeof(int) * numsSize);

    prefix[0] = 1;//计算前缀乘积
    for (int i = 1; i < numsSize; i++)
    {
        prefix[i] = prefix[i - 1] * nums[i - 1];//用上一位的前缀乘积乘以上一位的数，就是这一位的乘积
    }

    suffix[numsSize - 1] = 1;//计算后缀乘积
    for (int i = numsSize - 2; i >= 0; i--)
    {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }

    for (int i = 0; i < numsSize; i++)
    {
        answer[i] = prefix[i] * suffix[i];
    }
    free(prefix);
    free(suffix);
    return answer;
}